from Crypto.Util.number import long_to_bytes, inverse
import gmpy2

# 用户提供的参数
n = 91717197306065801430692774296739087369692505805873730729014813677164858033475119219496549179322145782790263228034134781592967028480301579462111507372893508636592832600206391905790511488678949157112322777098684707325311891056750963286494634489093620270797637437274546909400418496263799669541769586017282231886023275686719495040493703402244867906367008837217453500300992995258096509545406775279177918160331853363991834113918051468978309081085686108283547874975768959542753094631595260890420558364636303078263220001513817844063960023424429484568985727987064710176511050208253838039386390968276801658300795687804601169987051671314061987254212363117325786734328360418591971610392966867659045907550755979167652038093091970078722854251659581538266806207906127491377972897441916942048136016416739633568604447564119372465662628724153812001753748410162478969725179843125714619352895967577899670208386148053595763674920185320834513587
c = 23108886533446570872020909755641900356947493847891044150804220862211486326491971706435448761622169415139661878928224913976333510314336448940337410429358364930668139829928592529668292963027387644469478288972914226815180690096771951746297286742213772233222849955148332178748604312396371718173812097510261044590926364130009538926786724953078781179023997612212615391343990439872921361528517747700275371695937658958128759666192424696264306876062180553241654472104865168758800754398829940157821429340806270860129304323452617932918962620283443237641173000603550358778106863474195136519485531345183377464308279092379760531364034030760854381522739756338905572215597123741549768493220177173389970868309425490948920216103262840379934097953147391955089537672609825176272093624601261813994392924293258762828299757881538282236959849884840306493309190697864334857950458623192423892550873631196964551924143834939270415901966374552371883381
gift1 = 513
gift2 = 5077110719426498428662246006638349628986894614097694065336047422264042823893900747327210766546701290926253205743419412459378571920759093322149140413682875156857171051511499793127787270654329155934268596972449238336868326196360992252498463385

# 枚举中间的10位
for m in range(1024):
    # 构造p_candidate
    p_candidate = (gift2 << 20) + (m << 10) + gift1
    # 检查是否为素数且能整除n
    if gmpy2.is_prime(p_candidate) and n % p_candidate == 0:
        print(f"Found p: {p_candidate}")
        break

# 分解q*r
q_r = n // p_candidate
# Fermat分解法
def fermat_factor(q_r):
    m = gmpy2.isqrt(q_r) + 1
    while True:
        t = m*m - q_r
        #if t >= 0 and gmpy2.is_square(t):
        if 1:
            s = gmpy2.isqrt(t)
            return m - s, m + s
        m += 1

q, r = fermat_factor(q_r)
print(f"q = {q}, r = {r}")

# 计算φ(n)和d
phi = (p_candidate - 1) * (q - 1) * (r - 1)
d = inverse(0x10001, phi)
flag = long_to_bytes(pow(c, d, n)).decode()
print(f"Flag: {flag}")
